#include "StdAfx.h"
#include "QuickSorter.h"

namespace ftips {

	QuickSorter::QuickSorter(void)
	{
	}

	QuickSorter::~QuickSorter(void)
	{
	}

	// Function: sort array
	void QuickSorter::QuickSort(double src[], int order[], int l, int r) {
		if (l >= r)
			return;
		int mid = Partition(src, order, l, r);
		QuickSort(src, order, l, mid - 1);
		QuickSort(src, order, mid + 1, r);
	}

	// Function: partition
	int QuickSorter::Partition(double src[], int order[], int l, int r) {
		double x = src[l];
		int i = l;
		int j = r + 1;
		while (true) {
			while ((src[++i] < x) && (i < r));
			while (src[--j] > x);
			if (i >= j)
				break;		

			double tmp = src[i];
			src[i] = src[j];
			src[j] = tmp;			

			tmp = order[i];
			order[i] = order[j];
			order[j] = tmp;
		}
		src[l] = src[j];
		src[j] = x;

		double tmp = order[l];
		order[l] = order[j];
		order[j] = tmp;

		return j;
	}

}